package main;


import datatype.*;

/**
 * @author Artur Tolstenco
 *
 */

/**
 * Class that implements the algorithm of Dijkstra - Shortest Path
 */
public class DijkstraAlgorithm {
	public static DijkstraVertex[] searchShortestPath(Graph graph, Vertex sourceVertex) {
		PriorityQueue verticesQueue;
		DijkstraVertex[] treeAndDistances;
		int temp = graph.nodes().size();
		
		
		verticesQueue = new PriorityQueue(temp);
		treeAndDistances = new DijkstraVertex[temp];
		
		for (Vertex vertex : graph.nodes())
			treeAndDistances[vertex.getIndex()] = new DijkstraVertex(vertex, Double.POSITIVE_INFINITY, null);
		
		treeAndDistances[sourceVertex.getIndex()].setMinimumDistance(0.0d);
		
		for (Vertex vertex : graph.nodes())
			verticesQueue.add(vertex, treeAndDistances[vertex.getIndex()].getMinimumDistance());
		
		
		while (!verticesQueue.isEmpty()) {
			Vertex tempSourceVertex = verticesQueue.deleteMin();
						
			for (Edge edge : graph.adjacents(tempSourceVertex)) {
				Vertex targetVertex = edge.getTarget();
				double distanceThroughTargetVertex = treeAndDistances[tempSourceVertex.getIndex()].getMinimumDistance() + edge.getWeight();
				
				if (distanceThroughTargetVertex < treeAndDistances[targetVertex.getIndex()].getMinimumDistance()) {
					treeAndDistances[targetVertex.getIndex()].setParent(tempSourceVertex);
					treeAndDistances[targetVertex.getIndex()].setMinimumDistance(distanceThroughTargetVertex);
					verticesQueue.changePriority(targetVertex, treeAndDistances[targetVertex.getIndex()].getMinimumDistance());
				}
			}
		}
		
		return treeAndDistances;
	}
}
